import java.util.ArrayList;
import java.util.List;

/**
* @description: 1417. 重新格式化字符串
* @author hewei
* @date 2022/8/11 14:06
* @version 1.0
*/

public class Reformat {

    public String reformat1(String s) {
        List<Character> letterList = new ArrayList<>();
        List<Character> digitList = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                digitList.add(c);
            } else letterList.add(c);
        }
        if (Math.abs(letterList.size() - digitList.size()) >= 2) return "";
        return letterList.size() > digitList.size() ? process(letterList, digitList) : process(digitList, letterList);
    }

    public String process(List<Character> s1, List<Character> s2) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s2.size(); i++) {
            stringBuilder.append(s1.get(i));
            stringBuilder.append(s2.get(i));
        }
        if (s1.size() > s2.size()) stringBuilder.append(s1.get(s1.size() - 1));
        return stringBuilder.toString();
    }

    public String reformat(String s) {
        int digitCount = 0;
        for (int i = 0; i < s.length(); i++) {
            if (Character.isDigit(s.charAt(i))) ++ digitCount;
        }
        if (Math.abs(s.length() - digitCount - digitCount) >= 2) return "";
        boolean flag = digitCount > s.length() - digitCount;
        char[] chars = s.toCharArray();
        for (int i = 0, j = 1; i < chars.length; i += 2) {
            if (Character.isDigit(chars[i]) != flag) {
                while (Character.isDigit(chars[j]) != flag) j += 2;
                char temp = chars[i];
                chars[i] = chars[j];
                chars[j] = temp;
            }
        }
        return new String(chars);
    }
}
